{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 在限制的次数内查找最小/大值\n",
    "\n",
    "[@mjd507](https://github.com/mjd507) |\n",
    "[Switch to English](https://mp.weixin.qq.com/s/VJSvtcVfn8Cni-xhyKuu6w)\n",
    "\n",
    "From today on, I will only translate questions and solutions into Simplified Chinese. The original article was published in the Wechat Channel. Please visit it on your own if you need. Thank you!\n",
    "\n",
    "![Logo](images/Day76-1.png)\n",
    "\n",
    "给定一个长度为$n$的列表，其中$n \\gt 3$。在少于$2(n-1)$次比较内找到列表的最小值与最大值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 初始模板\n",
    "\n",
    "$2(n-1)$次源自最初的“打擂台”算法，每次遍历1个元素、进行2次判断，恰好需要$2(n-1)$次判断。\n",
    "\n",
    "下面这种算法将整个列表按桶深度为$2$分割成$\\left \\lceil \\frac{n}{2} \\right \\rceil$个桶，这使得遍历整个列表的次数降低为$\\left \\lceil \\frac{n}{2} \\right \\rceil$次。\n",
    "\n",
    "同时每个桶的比较只需要$3$次，所以算法整体比较次数需要$\\left \\lceil \\frac{3n}{2} \\right \\rceil$次，低于要求的$2(n-1)$次。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_min_max(nums: list) -> tuple:\n",
    "    # For Python, divisibility already has the ability to \"round down\"。\n",
    "    median = len(nums) // 2\n",
    "    maximum = minimum = nums[0]\n",
    "    for i in range(median):\n",
    "        first = nums[2 * i]\n",
    "        second = nums[2 * i + 1]\n",
    "        if first < second:\n",
    "            minimum = min(minimum, first)\n",
    "            maximum = max(maximum, second)\n",
    "        else:\n",
    "            minimum = min(minimum, second)\n",
    "            maximum = max(maximum, first)\n",
    "    if len(nums) % 2 == 1:\n",
    "        maximum = max(maximum, nums[-1])\n",
    "        minimum = min(minimum, nums[-1])\n",
    "    return (minimum, maximum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 测试用例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 8)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_min_max([3, 5, 1, 2, 4, 8])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
